{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Deep Learning Book (Simplified)\n",
    "## Part I - Applied Math and Machine Learning basics\n",
    "*This is a series of blog posts on the [Deep Learning book](http://deeplearningbook.org) where we are attempting to provide a summary of each chapter highlighting the concepts that we found to be most important so that other people can use it as a starting point for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer [this](http://www.deeplearningbook.org/contents/notation.html) for more clarity on notation.*\n",
    "\n",
    "## Chapter 4: Numerical Computation\n",
    "\n",
    "Since you are here, there's a high probability that you must have heard of **Gradient Descent**. It is that part of a Deep Learning pipeline which leads to the model being *trained*. This chapter outlines the various kinds of numerical computations generally utilized by Machine Learning algorithms and also describes various optimization algorithms (e.g. Gradient Descent, Newton's method), which are those class of algorithms that update the estimates of the solution iteratively, rather than solving it analytically to provide a closed-form solution.\n",
    "\n",
    "The sections present in this chapter are listed below: <br>\n",
    "\n",
    "**1. Overflow and Underflow?** <br>\n",
    "**2. Poor Conditioning** <br>\n",
    "**3. Gradient-Based Optimization** <br>\n",
    "**4. Constrained Optimization** <br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Overflow and Underflow\n",
    "\n",
    "There is a fundamental problem with representing infinitely many real numbers on a digital computer with a finite number of bit patterns, which is: it leads to rounding errors. Such rounding errors compound over certain operations and cause many theoretically correct algorithms to fail in practise. There are primarily two damaging forms of rounding errors:\n",
    "\n",
    "- **Underflow**: Underflow occurs when numbers near to zero are rounded down to zero. <br> \n",
    "The behaviour of certain functions like $\\frac{1}{x}$ , $log$, etc. can change dramatically due to this.\n",
    "\n",
    "- **Overflow**: Overflow occurs when a large number is approximated as $\\infty$ (or $-\\infty$).\n",
    "\n",
    "*Example* - Softmax\n",
    "![softmax](images/softmax.png)\n",
    "\n",
    "Assume every $x_i$ is equal to some $c$. <br> \n",
    "\n",
    "**Problems**:\n",
    "- $c$ is very negative: This leads to underflow when computing $exp(c)$ and thus $0$ in the denominator.\n",
    "- $c$ is very positive: This leads to overflow when computing $exp(c)$.\n",
    "\n",
    "**Solution**: \n",
    "\n",
    "Instead of computing $softmax(\\mathbf{x})$, we compute $softmax(\\mathbf{z})$, where $\\mathbf{z} = \\mathbf{x} - \\max_i x_i$. It can be proven that the value doesn't change after subtracting the same value from each of the elements. Now, the maximum value in $\\mathbf{z}$ is $0$, thus preventing overflow. Also, this ensures that atleast one element in the denominator is $1$, preventing underflow.\n",
    "\n",
    "*Food for thought*: This still doesn't prevent underflow in the numerator. Think of the case when the output from the softmax function is passed as input to another function, e.g., $log$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Poor Conditioning\n",
    "\n",
    "Conditioning measures how rapidly the output of a function changes with small changes in the input. Large conditioning means poor conditioning as rounding errors can lead to large changes in output.\n",
    "For e.g., let's observe: $ f(x) = A^{-1}x$. Given that $A \\in \\mathbb{R}^{n \\hspace{.1cm} \\text{x} \\hspace{.1cm} n}$ has an eigen value decomposition, its **condition number** is given by:\n",
    "\n",
    "![condition number](images/condition_number.png)\n",
    "\n",
    "which is equal to the ratio of the largest and the smallest eigen values. Having a large condition number signifies that matrix inversion is highly sensitive to errors in the input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Gradient Based Optimization\n",
    "\n",
    "Most optimization problems are phrased in terms of minimizing $f(x)$. Maximization can be achieved via a minimization algorithm by minimizing $-f(x)$.\n",
    "\n",
    "The **derivative** of a function $f$, denoted as $f'(x)$, specifies how a small change in input reflects as a change in output: $f(x + \\epsilon) \\approx f(x) + \\epsilon * f'(x)$. The derivative is useful for minimizing a function because it tells us how to change $x$ in order to make a small improvement in $y$. E.g. for a small enough $\\epsilon$, $f\\Big(x - \\epsilon\\, sign\\big(f'(x)\\big) \\Big)$ will be smaller than $f(x)$. This technique is called **gradient descent**.\n",
    "\n",
    "![gradient descent](images/gradient_descent.png)\n",
    "\n",
    "Points where $f'(x)=0$ are called **critical** or **stationary** points. Types of critical points:\n",
    "\n",
    "![critical points](images/critical_points.png)\n",
    "\n",
    "For functions with multiple inputs, **partial derivative** $\\frac{\\delta}{\\delta x_i}f(x)$ measures how $f$ changes as only the variable $x_i$ changes at point $x$. The **gradient** of $f$ is a vector containing all partial derivatives denoted $\\nabla_x\\, f(x)$. The **directional derivative** in a direction ***u*** (unit vector) is the slope of $f$ in the direction *u*.\n",
    "\n",
    "i.e. the directional derivative is the value of $\\frac{\\delta}{\\delta \\alpha}f(x+\\alpha*u)$ evaluated as $\\alpha \\rightarrow 0$.\n",
    "\n",
    "Using the chain rule:\n",
    "\n",
    "$\\frac{\\delta}{\\delta \\alpha}f(x+\\alpha*u) = \\big(\\frac{\\delta}{\\delta \\alpha}(x+\\alpha*u)\\big)^T\\frac{\\delta}{\\delta(x+\\alpha*u)}f(x+\\alpha*u)$\n",
    "\n",
    "as $\\alpha$ tends to 0 the expression reduces to $u^T\\nabla_x\\, f(x)$. To minimize $f$ we need to find the direction *u* in which $f$ decreases the fastest i.e.:\n",
    "\n",
    "![partial derivative](images/partial_derivative.png)\n",
    "\n",
    "Ignoring terms not relating to *u* we see that function *f* is decreased most when $cos\\theta = -1$ i.e. we move in the direction opposite to the gradient. This is the method of **steepest descent** or **gradient descent**. Steepest descent proposes the new point: $x' = x - \\epsilon \\nabla_x\\, f(x)$ where $\\epsilon$ is the **learning rate**. $\\epsilon$ can be a small constant or can be solved analytically to make the gradient vanish. Another approach is to try different values of $\\epsilon$ and choose the value that causes the most decrease (**line search**).\n",
    "\n",
    "The general concept of repeatedly making a small move in the locally best direction can be generalized to discrete spaces (**hill climbing**)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1 Jacobian and Hessian Matrices\n",
    "\n",
    "If we have a function $f: \\mathbb{R}^m \\rightarrow \\mathbb{R}^n$, then the **Jacobian** matrix $J \\in \\mathbb{R}^{n\\, \\times\\, m}$ of $f$ is defined such that $J_{i,j} = \\frac{\\delta}{\\delta x_j}f_i(x)$\n",
    "\n",
    "The **second derivative** tells us how the first derivative changes with small changes in input. It is a measurement of **curvature**. The **Hessian** matrix **H**(f)(**x**) is defined such that\n",
    "\n",
    "$H(f)(x)_{i,j} = \\frac{\\delta^2}{\\delta x_i \\delta x_j}f(x)$\n",
    "\n",
    "Hessian is the Jacobian of the gradient.\n",
    "\n",
    "Anywhere that the second partial derivatives are continuous, the differential operators are commutative. This means that $H_{i,j} = H_{j,i}$ and the Hessian is symmetric. This is the most common case in the deep learning regime.\n",
    "\n",
    "Hessian matrix is real and symmetric $\\Rightarrow$ it can be decomposed into a set of real eigenvalues and orthogonal eigenvector basis\n",
    "\n",
    "Second derivative in a specific direction **d**(unit vector) is $\\mathbf{d^THd}$.\n",
    "\n",
    "When **d** is an eigenvector of H, the second derivative is the corresponding eigenvalue. In the general case, the second derivative is given by the weighted average of eigenvalues.\n",
    "\n",
    "Second-order Taylor series approximation of $f(\\mathbf{x})$ around the point $\\mathbf{x^{(0)}}$:\n",
    "\n",
    "$f(\\mathbf{x}) \\approx f(\\mathbf{x^{(0)}}) + (\\mathbf{x}-\\mathbf{x^{(0)}})^T\\mathbf{g} + \\frac{1}{2}(\\mathbf{x}-\\mathbf{x^{(0)}})^T\\mathbf{H}(\\mathbf{x}-\\mathbf{x^{(0)}})$ where **g** is the gradient and **H** is the Hessian\n",
    "\n",
    "Using gradient descent, the new point will be $(\\mathbf{x^{(0)}} - \\epsilon \\mathbf{g})$. Substituting in the above equation:\n",
    "\n",
    "$f(\\mathbf{x^{(0)}} - \\epsilon \\mathbf{g}) \\approx f(\\mathbf{x^{(0)}}) - \\epsilon \\mathbf{g}^T\\mathbf{g} + \\frac{1}{2}\\epsilon^2\\mathbf{g}^T\\mathbf{H}\\mathbf{g}$\n",
    "\n",
    "Breakdown: Orignal function - expected decrease due to gradient + correction due to function curvature. When the last term is large, the update actually moves the point uphill. When it is zero or negative, the equation gives that larger $\\epsilon$ will always decrease the function value, however, moving too far from $\\mathbf{x^{(0)}}$ will invalidate the Taylor approximation. When $\\mathbf{g}^T\\mathbf{H}\\mathbf{g}$ is positive, optimal step size is given by:\n",
    "\n",
    "$\\epsilon^* = \\frac{\\mathbf{g}^T\\mathbf{g}}{\\mathbf{g}^T\\mathbf{H}\\mathbf{g}}$\n",
    "\n",
    "In the worst case, **g** aligns with an eigenvector of **H** corresponding to the largest eigenvalue ($\\lambda_{max}$) and the optimal step size will be $\\frac{1}{\\lambda_{max}}$. The eigenvalues of H give the scale of learning rate.\n",
    "\n",
    "At critical point, where $f'(x) = 0$, the second derivative test for the univariate case is given as:\n",
    "\n",
    "| $f''(x)\\, $ | conclusion |\n",
    "| --- | --- |\n",
    "|  $>0$ | local minimum |\n",
    "|  $<0$ | local maximum |\n",
    "|  $=0$ | inconclusive |\n",
    "\n",
    "In multiple dimensions, for Hessian matrix:\n",
    "\n",
    "| eigenvalue | conclusion |\n",
    "| --- | --- |\n",
    "| all positive | local minimum |\n",
    "| all negative | local maximum |\n",
    "| atleast one positive and negative each | saddle |\n",
    "| all non-zero same sign, atleast one zero | inconclusive |\n",
    "\n",
    "![saddle](images/saddle.png)\n",
    "\n",
    "Explanation of `all_positive` (rest follow similarly): When all the eigenvalues are positive, the Hessian is positive definite. Hence, the directional second derivative in each direction is positive, and infering from the univariate second derivative test, we get that the critical point is a local minimum. The image above shows a saddle point.\n",
    "\n",
    "When the Hessian has a poor condition number, gradient descent performs poorly, as it is confused between one direction where the gradient increases significantly, and another direction where it increases slowly. Gradient descent is unaware of this change in the derivative, so it does not know that it needs to explore preferentially in the direction where the derivative remains negative for longer.\n",
    "\n",
    "Solution to the issue: use information from the Hessian matrix. An example is the **Newton's method** based on second degree Taylor expansion.\n",
    "\n",
    "$f(\\mathbf{x}) = f(\\mathbf{x^{(0)}}) + (\\mathbf{x}-\\mathbf{x^{(0)}})^T\\nabla_xf(\\mathbf{x^{(0)}}) + \\frac{1}{2}(\\mathbf{x}-\\mathbf{x^{(0)}})^T\\mathbf{H}(f)(\\mathbf{x^{(0)}})(\\mathbf{x}-\\mathbf{x^{(0)}})$\n",
    "\n",
    "Taking gradient wrt **x** and setting L.H.S. to zero:\n",
    "\n",
    "$0 = \\nabla_xf(\\mathbf{x^{(0)}}) + \\mathbf{H}(f)(\\mathbf{x^{(0)}})\\mathbf{x} - \\mathbf{H}(f)(\\mathbf{x^{(0)}})\\mathbf{x^{(0)}}$\n",
    "\n",
    "$\\mathbf{x} = \\mathbf{x^{(0)}} - \\mathbf{H}(f)(\\mathbf{x^{(0)}})^{-1}\\nabla_xf(\\mathbf{x^{(0)}})$\n",
    "\n",
    "This method consists of iteratively jumping to the minimum of a locally approximated quadratic function $\\rightarrow$ converges faster than gradient descent. However, unlike gradient descent, solution of Newton's method is attracted to saddle points as well.\n",
    "\n",
    "To treat functions in deep learning, we assume that they are Lipschitz continuous or have lipschitz continuous derivatives. (weak constraint) A **Lipschitz continuous** function satisfies for a Lipschitz constant $\\mathcal{L}$ the bound:\n",
    "\n",
    "$\\forall \\mathbf{x}\\, ,\\forall \\mathbf{y}\\, ,|f(\\mathbf{x}) - f(\\mathbf{y})| \\leq \\mathcal{L}||\\mathbf{x}-\\mathbf{y}||_2$\n",
    "\n",
    "This property is useful because it enables us to quantify our assumption that a small change in the input made by an algorithm such as gradient descent will have a small change in the output.\n",
    "\n",
    "**Convex optimization** algorithms are able to provide many more guarantees by making stronger restrictions. These algorithms are applicable only to convex functions—functions for which the Hessian is positive semideﬁnite everywhere. It is sometimes used as a subroutine in deep learning algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Constrained Optimization\n",
    "\n",
    "It might be the case that although we want to maximize (or minimize) $f(x)$, but aren't allowed to use all possible values of $x$, say $x \\in \\mathbb{S}$, for some set $\\mathbb{S}$. This now becomes a problem of **Constrained Optimization**. The points $\\mathbf{x}$ in $S$ are called **feasible points**. \n",
    "\n",
    "An example of such a constraint can be the L2-norm constraint, e.g. $|| \\hspace{.1cm} x \\hspace{.1cm}||^2 < 1$. This is useful as we often want the values for our weights to be small (i.e. close to $0$).\n",
    "\n",
    "*Approach*: Design a separate, unconstrained optimization problem, whose solution can be converted to the original constrained optimization problem. E.g. in the above described constrained optimization problem, we could instead minimize:\n",
    "$$g(\\theta) = f([\\cos\\theta, \\sin\\theta]^T)$$\n",
    "\n",
    "with respect to $\\theta$ and return ($\\cos\\theta, \\sin\\theta$).\n",
    "\n",
    "\n",
    "General solution: **Karush–Kuhn–Tucker(KKT)** approach which introduces a **generalized Lagrangian**.\n",
    "\n",
    "Approach: \n",
    "\n",
    "We use $m$ functions $g^{(i)}(x)$ and $n$ functions $h^{(j)}(x)$ to describe $\\mathbb{S}$,  such that any element $x \\in \\mathbb{S}$ satisfies: \n",
    "$$g^{(i)}(x) = 0 \\hspace{.1cm} \\text{and} \\hspace{.1cm} h^{(j)}(x) \\leq 0 \\hspace{.1cm} \\forall \\hspace{.1cm} i, j$$\n",
    "\n",
    "There are two constraints specified here. I'll explain them with an example. Let's take $g(x)$ as $x - 2$ and $h(x)$ as $x-3$. <br>\n",
    "Then for $x = 2$, we have the following:\n",
    "\n",
    "- **Equality constraints**: $g^{(i)}(x) = 0$. Here, $g(2) = 0$. Hence, $x = 2$ satisfies the equality constraints.\n",
    "- **Inequality constraints**: $h^{(i)}(x) \\leq 0$. Here, $h(2) = -1 < 0$. Hence, $x = 2$ satisfies the inequality constraints.\n",
    "\n",
    "Note that for $x = 3$, $h(x)$ is an equality constraint that it satisfies whereas $g(x)$ is neither.\n",
    "\n",
    "New paramaters (called KKT multipliers): $\\lambda_i$, $\\alpha_j$ for each constraint.  <br>\n",
    "Generalized Lagrangian:\n",
    "\n",
    "\n",
    "![lagrangian](images/Lagrangian.png)\n",
    "\n",
    "Now, let: $Y =\\max\\limits_{\\alpha} \\max\\limits_{\\lambda} L(x, \\lambda, \\alpha)$\n",
    "Then, $\\min\\limits_x(f(x)) = \\min\\limits_x(Y)$\n",
    "\n",
    "This is because, if the constraints are satisfied, $Y = f(x)$ and if it isn't, $Y = \\infty$. This ensures that only feasible points are optimal. For finding the maximum of f(x), we can use the same generalized Lagrangian applied on $-f(x)$. \n",
    "\n",
    "The inequality constraints need to be observed more closely. Suppose the optimal point comes out to be $x^*$. If $h^{(i)}(x^*) = 0$, then the constraint is said to be **active**. However, if the constraint is inactive, i.e. $h^{(i)}(x^*) < 0$, then even if we remove the constraint, $x^*$ continues to be a local solution. Also, by definition, an inactive $h^{(i)}$ is negative and hence $\\max\\limits_{\\alpha} \\max\\limits_{\\lambda} L(x, \\lambda, \\alpha) \\Rightarrow \\alpha_i = 0$. Thus, either $\\alpha_i = 0$ or $h^{(i)}(x^*) = 0$ (in the case of active constraint). Hence, $\\mathbf{\\alpha} \\odot h{(x)} = 0$.\n",
    "\n",
    "Intuition: \n",
    "\n",
    "The relation of the optimal point can satisfy only of these two conditions:\n",
    "\n",
    "- The point is at the boundary of the constraint (i.e. active), then the corresponding KKT multiplier should be used.\n",
    "\n",
    "- The constraint has no influence in the evaluation of the point and hence, the corresponding KKT multiplier is zeroed out.\n",
    "\n",
    "The optimal points satisfy the following KKT conditions, which are necessary but not always sufficient:\n",
    "\n",
    "![kkt](images/kkt.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
